package 牛客网编程.剑指offer.二维递增数组查找数;

import org.junit.Test;

/**
 * @author Veng Su 1344114844@qq.com
 * @date 2018/7/13 22:08
 */

/**
 题目描述
 在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

 */
public class Solution {
    public boolean Find(int target, int[][] array) {

        int res=-1;
        for (int[] i : array
                ) {
            if (i.length<=0){
                return false;
            }
            res =binSearch(i,0,i.length-1,target);
            if (res>=0){
                return true;
            }
        }
        return false;
    }

    /**
     * 二分查找递归实现。
     *
     * @param srcArray 有序数组
     * @param start    数组低地址下标
     * @param end      数组高地址下标
     * @param key      查找元素
     * @return 查找元素不存在返回-1
     */
    public static int binSearch(int srcArray[], int start, int end, int key) {
        int mid = (end - start) / 2 + start;
        if (srcArray[mid] == key) {
            return mid;
        }
        if (start >= end) {
            return -1;
        } else if (key > srcArray[mid]) {
            return binSearch(srcArray, mid + 1, end, key);
        } else if (key < srcArray[mid]) {
            return binSearch(srcArray, start, mid - 1, key);
        }
        return -1;
    }
    /**
     * 二分查找普通实现。
     * @param srcArray 有序数组
     * @param key 查找元素
     * @return  不存在返回-1
     */
    public static int binSearch(int srcArray[], int key) {
        int mid;
        int start = 0;
        int end = srcArray.length - 1;
        while (start <= end) {
            mid = (end - start) / 2 + start;
            if (key < srcArray[mid]) {
                end = mid - 1;
            } else if (key > srcArray[mid]) {
                start = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }
    public int halfSearch(int[] array,int key,int end,int start){

        int mid=(end-start)/2+start;
        if (array[mid]==key){
            return mid;
        }
        if (end<=start){
            return -1;
        }else if (key>array[mid]){
            halfSearch(array,key,end,mid+1);
        }else if (key<array[mid]){
            halfSearch(array,key,start,mid-1);
        }

        return -1;
    }


    @Test
    public void test() {
        Solution solution = new Solution();
        int[][] array = {{1, 2, 8, 9}, {2, 4, 9, 12, 12}, {4, 7, 10, 13}, {6, 8, 11, 15}};
        System.out.println(solution.Find(22, array));
    }
}